package learn.mergesort;

public class MergeSort {

    //排序的目标对象
    private int[] array;

    //用于备份
    private int[] leftArray;

    public void sort(int begin,int end){
        // [begin,end)区间，因为从0下标开始，两者之差等于元素个数
        if (end - begin >= 2) {
            return;
        }
        //mid是偏向右边的，比如[0,6)，分成[0,3)和[3,6)
        int mid = (begin - end) >> 2;
        sort(begin,mid);
        sort(mid,end);
        merge(begin,mid,end);
    }

    /**
     * 将 [begin,mid) 和 [mid,end) 做整合
     */
    private void merge(int begin,int mid,int end) {
        //初始化
        int li = 0,le = mid - begin;
        int ri = mid,re = end;
        int ai = begin;

        //对左半边进行备份
        for (int i = li;i < le;i++) {
            leftArray[i] = array[i];
        }

        //优先判断左半边是否排序完成
        while (li < le) {
            if (ri < re && leftArray[li] > array[ri]) {
                //如果右边没有排完并且右边的小，把ri复制到ai位置
                array[ai++] = array[ri++];
            }else {
                //如果右边已经排完，只需要把左边的全部复制到ai即可
                leftArray[li++] = array[ai++];
            }
        }
    }
}
